package algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Date 2021/9/2 16:12
 * @Author 李明杰
 * @Description
 */

public class QuickSort {
    public static void main(String[] args) {
        Integer[] a = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        QuickSort.sort(a);
        System.out.println(Arrays.toString(a));//{1, 2, 3, 4, 5, 6, 7, 8, 9}
    }

    /*
      比较v元素是否小于w元素
   */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }


    /*
        数组元素i和j交换位置
    */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //对数组内的元素进行排序
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }

    //对数组a中从索引lo到索引hi之间的元素进行排序
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int partition = partition(a, lo, hi);
        sort(a, lo, partition - 1);
        sort(a, partition + 1, hi);
    }

    //对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引
    public static int partition(Comparable[] a, int lo, int hi) {

        Comparable key = a[lo];
        int left = lo;
        int right = hi + 1;
        while (true) {
            while (!less(key, a[++left])) {

                if (left == hi) {
                    break;
                }
            }
            while (less(key, a[--right])) {

                if (right == lo) {
                    break;
                }
            }
            //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (left >= right) {
                break;
            } else {
                exch(a, left, right);
            }

        }
        exch(a, lo, right);
        return right;
    }

}
